括号Java组输入的有效括号匹配方法

Question

编辑：我应该提到程序必须是严格非递归的

我正在尝试创建一个方法，将组分配给匹配的括号。例如，输入：m (a (b c) (d (e (f g h) i) j) k) n输出为：

Inputted text: m (a (b c) (d (e (f g h) i) j) k) n
group 0 =  m (a (b c) (d (e (f g h) i) j) k) n
group 1 = (a (b c) (d (e (f g h) i) j) k)
group 2 = (b c)
group 3 = (d (e (f g h) i) j)
group 4 = (e (f g h) i)
group 5 = (f g h)

我创建了以下方法，但正如您所看到的，它将第一个遇到的左括号与第一个遇到的右括号相匹配，而不是每个左括号表示新组的开始。我无法找到一种简单的方法来复制上述输出而不重新开始。有什么想法吗

    public class Matching {

    public static String[] group(String s){
        Stack<Integer> indexStack = new Stack<Integer>();
        String[] groupArray = new String[15];
        int count = 0;

        for(int i = 0; i != s.length(); i++){
            /*
             * If character in index position is a left parenthesis, push the current
             * index onto stack. If a right parenthesis is encountered, pop the stack and
             * store its index temporarily. Use index and current position at right
             * parenthesis to create a substring.   
             */
            if(s.charAt(i) == '(')
                indexStack.push(i);
            else if( s.charAt(i) == ')' ){

                try{
                    int index = indexStack.pop();
                    groupArray[count++] = s.substring(index, i + 1);
                }
                catch(Exception e){ //An exception results from popping empty stack 
                    System.out.println("Unbalanced in input " + s +  
                            " at index " + i + "\n");

                    return null; //return null to caller
                }
            }
        }
        //If stack not empty at the end of loop, return null to caller
        if(!indexStack.isEmpty()){ 
                System.out.println("Unbalanced in input " + s + 
                        " at index " + indexStack.pop() + "\n");

                return null; 
        }
        //initial input that starts with a character other than ( needed to be added.
        if (s.charAt(0) != '(')
            groupArray[count++] = s;

        return groupArray;
    }
}

Answer 1

import java.util.Stack;

public class Matching {

    public static String[] group(String s){
        Stack<Integer> indexStack = new Stack<Integer>();
        String[] groupArray = new String[15];
        int[] tracker = new int[s.length()]; //helper for proper grouping
        int count = 0;

        for(int i = 0; i != s.length(); i++){
            /*
             * If character in index position is a left parenthesis, push the current
             * index onto stack. If a right parenthesis is encountered, pop the stack and
             * store its index temporarily. Use index and current position at right
             * parenthesis to create a substring.   
             */
            if(s.charAt(i) == '('){
                indexStack.push(i); 
                tracker[count++] = i; //left parenthesis signify a new group
            }
            else if( s.charAt(i) == ')' ){
                try{
                    int index = indexStack.pop();

                    int j = 0; //find where corresponding index was placed in array
                    while(tracker[j] != index)
                        j++;

                    groupArray[j] = s.substring(index, i + 1);
                }
                catch(Exception e){ //An exception results from popping empty stack 
                    System.out.println("Unbalanced in input " + s +  
                            " at index " + i + "\n");

                    return null; //return null to caller
                }
            }
        }
        //If stack not empty at the end of loop, return null to caller
        if(!indexStack.isEmpty()){ 
                System.out.println("Unbalanced in input " + s + 
                        " at index " + indexStack.pop() + "\n");

                return null; 
        }
        //initial input that starts with a character other than ( needed to be added.
        if (s.charAt(0) != '(')
            groupArray[count++] = s;

        return groupArray;
    }
}

我使用另一个数组来跟踪左括号中出现的情况，为这个问题添加了一个非常糟糕的修复方法。如果我的教授看到了我没有作弊

Answer 2

不需要使用递归。 如果输出元素的顺序不受限制，则尝试使用此选项（请注意，输入中的所有字符都有一次迭代）：

private List<String> findSubSets(final String expresion) {
    final List<String> result = new ArrayList<>();
    final Stack<StringBuilder> stack = new Stack<>();
    StringBuilder builder = new StringBuilder();
    for (char c : expresion.toCharArray()) {
        if (c == '(') {
            stack.push(builder);
            builder = new StringBuilder();
        }
        builder.append(c);
        if (c == ')') {
            final String value = builder.toString();
            final StringBuilder parent = stack.pop();
            parent.append(value);
            result.add(value);
            builder = parent;
        }
    }
    if (!expresion.startsWith("(")) {
        result.add(builder.toString());
    }
    return result;
}

输出

Group 0 = (b c)
Group 1 = (f g h)
Group 2 = (e (f g h) i)
Group 3 = (d (e (f g h) i) j)
Group 4 = (a (b c) (d (e (f g h) i) j) k)
Group 5 = m (a (b c) (d (e (f g h) i) j) k) n

p.S. 算法假设输入格式正确——不均匀的(和)计数可能会导致EmptyStackException

Answer 3

更好的方法是使用正则表达式和递归。这减少了代码长度，并利用了java提供的实用程序

package test;

import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Grouping {

    static Pattern pattern = Pattern.compile("(\\(.*\\))");
    static Pattern subPattern = Pattern.compile("^(\\((\\w|\\s)*\\))");
    static Matcher matcher;
    static Matcher subMatcher;

    public static void main(String[] args) {
        String STRING_GROUP = "m (a (b c) (d (e (f g h) i) j) k) n";
        findMatchingGroup(STRING_GROUP);
    }

    public static void findMatchingGroup(String STRING_GROUP) {

        matcher = pattern.matcher(STRING_GROUP);
        // System.out.println("STRING : " + STRING_GROUP);

        while (matcher.find()) {
            String group = matcher.group(1);

            boolean ifSubString = false;
            subMatcher = subPattern.matcher(group);

            /**
             * I am trying to find if a subgroup exists at the beginning of the
             * string if yes then processes the string after the group. else cut
             * the string from both the ends to eliminate parenthesis for the
             * next iteration
             */

            if (subMatcher.find()) {
                System.out.println(subMatcher.group(1));
                ifSubString = true;
                findMatchingGroup(matcher.group(1).substring(
                        subMatcher.group(1).length() - 1));

            } else {
                System.out.println(group);
            }

            if (ifSubString == false) {
                findMatchingGroup(group.substring(1, group.length() - 2));
            }
        }

    }
}

Answer 4

当我更改代码的输入时，我遇到了一个错误。此外，在sys.out上还有多余的空值

我没有试图修复您的代码，但以下是一种分组方法：

import java.util.ArrayList;
import java.util.HashMap;

public class Match {

    public static void main(String[] args) {

        match("m(a(bc)(d(e(fgh)i)j)k)n");
    }

    public static void match(String string) {

        final int stringLength = string.length();
        final HashMap<Integer, Group> group = new HashMap<Integer, Group>();
        final ArrayList<Integer> counter = new ArrayList<Integer>();
        group.put(0, new Group(0, stringLength - 1));
        for (int i = 0; i < stringLength; i++) {
            final char charAt = string.charAt(i);
            if (charAt == '(') {
                group.put(i, new Group(i, 0));
                counter.add(i);
            } else if (charAt == ')') {
                final int counterIndex = counter.size() - 1;
                group.get(counter.get(counterIndex)).end = i;
                counter.remove(counterIndex);
            }
        }
        for (Group g : group.values())
            System.out.println(g.start + " --- " + g.end);
    }
}

class Group {

    int start;
    int end;

    Group(int s, int e) {

        this.start = s;
        this.end = e;
    }
}

你会得到开始&；组的结束点，然后您可以根据需要sys.out